class Solution(object):
    def minMutation(self, startGene, endGene, bank):
        """
        :type startGene: str
        :type endGene: str
        :type bank: List[str]
        :rtype: int
        """
        gene_map = self.build_map(startGene, endGene, bank)
        return self.bfs(gene_map, startGene, endGene)

    def bfs(self, gene_map, startGene, endGene):
        result = 0
        visited = set()

        queue = [startGene, None]

        while len(queue) != 0:
            it = queue.pop(0)
            if it == None:
                result = result + 1
                if len(queue) != 0:
                    queue.append(None)
            if it in visited or it not in gene_map:
                continue
            visited.add(it)
            if it == endGene:
                return result
            for t in gene_map[it]:
                queue.append(t)
        return -1

    def build_map(self, startGene, endGene, bank):
        result = {}
        for g in bank:
            result[g] = []
            if self.check_distance(startGene, g):
                self.add_edge(result, startGene, g)
            for h in bank:
                if g != h and self.check_distance(g, h):
                    self.add_edge(result, g, h)
            if self.check_distance(g, endGene):
                self.add_edge(result, g ,endGene)
        if self.check_distance(startGene, endGene):
            self.add_edge(result, startGene, endGene)
        return result

    def add_edge(self, result, s, t):
        if s in result:
            result[s].append(t)
        else:
            result[s] = [t]

    def check_distance(self, s, t):
        diff = 0
        for i in range(len(s)):
            if s[i] != t[i]:
                diff = diff + 1
            if diff > 1:
                return False
        return diff == 1

if __name__ == '__main__':
    print(Solution().minMutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"]))
